/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年04月17日
*   描    述：
*
================================================================*/

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
  int val;
  struct ListNode* next;
};

struct ListNode* reverseLinkedList(struct ListNode* head) {
  struct ListNode* prev = NULL;
  struct ListNode* curr = head;

  while (curr != NULL) {
    struct ListNode* nextNode = curr->next;
    curr->next = prev;
    prev = curr;
    curr = nextNode;
  }

  return prev;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
  struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
  dummy->next = head;
  struct ListNode* prev = dummy;
  struct ListNode* curr = head;

  int count = 0;
  while (curr != NULL) {
    count++;

    if (count % k == 0) {
      struct ListNode* nextGroup = curr->next;
      curr->next = NULL;

      struct ListNode* reversedList = reverseLinkedList(prev->next);
      prev->next = reversedList;

      while (prev->next != NULL) {
        prev = prev->next;
      }

      prev->next = nextGroup;
      curr = nextGroup;
    } else {
      curr = curr->next;
    }
  }

  struct ListNode* newHead = dummy->next;
  free(dummy);
  return newHead;
}

// 测试代码
void printLinkedList(struct ListNode* head) {
  struct ListNode* curr = head;
  while (curr != NULL) {
    printf("%d ", curr->val);
    curr = curr->next;
  }
  printf("\n");
}

int main() {
  struct ListNode* currNode = NULL;
  struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));

  head->val = 1;
  head->next = (struct ListNode*)malloc(sizeof(struct ListNode));
  currNode = head->next;

  currNode->val = 2;
  currNode->next = (struct ListNode*)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 3;
  currNode->next = (struct ListNode*)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 4;
  currNode->next = (struct ListNode*)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 5;
  currNode->next = (struct ListNode*)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 6;
  currNode->next = (struct ListNode*)malloc(sizeof(struct ListNode));
  currNode = currNode->next;

  currNode->val = 7;
  currNode->next = NULL;

  int k = 3;

  printf("原始链表：");
  printLinkedList(head);

  struct ListNode* reversed = reverseKGroup(head, k);

  printf("翻转后的链表：");
  printLinkedList(reversed);

  // 释放链表内存
  struct ListNode* curr = reversed;
  while (curr != NULL) {
    struct ListNode* temp = curr;
    curr = curr->next;
    free(temp);
  }

  return 0;
}
